package star;

import java.io.File;
import java.net.URL;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class star {

//    //快慢指针，龟兔跑，判断是否有环
//    public boolean hasCycle(ListNode head) {
//        ListNode slow = head,fast = head;
//        while(fast != null && fast.next != null) {
//            slow = slow.next; //龟走一步
//            fast = fast.next.next;//兔走两步
//            if(slow == fast){ //快慢相等则说明有环，兔套圈龟
//                return true;
//            }
//        }
//        return false;
//    }

    //求满足最多只有k个‘0’或‘1’的子字符串
    //子字符串的个数统计方式可以通过活动窗口累加统计
    //反复理解，
    public int countKConstraintSubstrings(String S, int k) {
        char[] s = S.toCharArray();
        int n = s.length;
        int left = 0;
        int ans = 0;
        int[] cnt = new int[2];
        for(int i=0; i<n ; i++){
            //s[i]&1 == s[i]%2
            cnt[s[i]&1]++;
            //条件不符合则，滑动左边的窗口，直至符合条件
            while(cnt[0] > k && cnt[1] > k){
                cnt[s[left] & 1]--;
                left++;
            }
            ans += i-left+1;
        }
        System.out.println(ans);
        return ans ;
    }

    //利用反射类加载器，获取一个包内的所有类名
    public void getPackage(){
        ClassLoader classLoader = Thread.currentThread().getContextClassLoader();
        String path = "star/";
        URL resource = classLoader.getResource(path.replace('.', '/'));
        if(resource != null){
            File directory = new File(resource.getFile());
            for(File file : directory.listFiles()){
                if(file.isDirectory()){continue;}
                String className = file.getName().substring(0, file.getName().length()-6);
                try{
                    Class<?> cls = Class.forName("star."+className);
                    System.out.println(cls);
                }catch (ClassNotFoundException e)
                {
                    e.printStackTrace();
                }
            }
        }
    }

    //1749. 任意子数组和的绝对值的最大值，
    //难点判断累加大小的条件
    public int maxAbsoluteSum(int[] nums) {
        int max = 0;
        int min = 0;
        int ans = 0;
        for(int x : nums){
            max = Math.max(max,0)+x;
            min = Math.min(min,0)+x;
            ans = Math.max(ans,Math.max(max,-min));
        }
        return ans;
    }

    //54.螺旋矩阵，
    //DIRS方向巧妙，判断下一步然后再走一步，
    //涉及方向可以考虑DIRS
    private static final int[][] DIRS = {{0,1},{1,0},{0,-1},{-1,0}};//右下左上
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new ArrayList<>(m*n);
        int i = 0;int j = 0;int di = 0;
        for(int k = 0 ; k<m*n ; k++){
            ans.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;//访问过的
            int x = i+DIRS[di][0];
            int y = j+DIRS[di][1];//下一步的位置
            //如果xy出界或已经访问过
            if(x<0 || x>=m || y<0 || y>=n || matrix[x][y] == Integer.MAX_VALUE){
                di=(di+1)%4;//右转90°
            }
            i += DIRS[di][0];
            j += DIRS[di][1];//走一步
        }
        return ans;
    }


    //30. 串联所有单词的子串，
    //滑动窗口难题
    public List<Integer> findSubstring(String s, String[] words) {
        int n = words.length;
        int len = words[0].length();
        List<Integer> ans = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for(String word: words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        //窗口是right+len整个len移动的，所以外层循环len次后就会重复
        for(int i=0 ; i<len ; i++){
            int left = i;
            int right = i;
            Map<String,Integer> winMap = new HashMap<>();
            while(right+len <= s.length()){
                String word = s.substring(right,right+len);
                winMap.put(word,winMap.getOrDefault(word,0)+1);
                right += len;
                while(winMap.get(word) > map.getOrDefault(word,0)){
                    String leftWord = s.substring(left,left+len);
                    winMap.put(leftWord,winMap.get(leftWord)-1);
                    left += len;
                }
                int count = (right-left)/len;
                if(count == n){
                    ans.add(left);
                }
            }
        }
        return ans;
    }
}
